//来源于力扣743
class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        int[][] g = new int[n][n];
        int INF = Integer.MAX_VALUE / 2;
        for (int i = 0; i < n; i++) {
            Arrays.fill(g[i], INF);
        }

        for (int i = 0; i < times.length; i++) {
            int[] temp = times[i];
            int x = temp[0] - 1;
            int y = temp[1] - 1;
            g[x][y] = temp[2];
        }

        boolean[] visited = new boolean[n];
        int[] dist = new int[n];
        Arrays.fill(dist, INF);
        dist[k - 1] = 0;
        //一次加入一个结点到路径中
        for (int i = 0; i < n; i++) {
            int cur = -1;
            //1.从未加入的结点中选取dist最小的,收录进来
            for (int j = 0; j < n; j++) {
                if (!visited[j] && (cur == -1 || dist[cur] > dist[j])) {
                    cur = j;
                }
            }
            visited[cur] = true;
            //2.更新收录结点周边的结点的dist

            for (int kl = 0; kl < n; kl++) {
                dist[kl] = Math.min(dist[kl], dist[cur] + g[cur][kl]);
            }
        }

        int result = 0;
        for (int i = 0; i < n; i++) {
            if (dist[i] == INF) {
                return -1;
            }
            result = Math.max(result, dist[i]);
        }

        return result;
    }
}